#include <iostream>
#include <time.h>

const int capacity = 10;
class MinHeap
{
public:
    MinHeap():size(0) {}
    void Insert(int value)
    {
        array[size] = value;
        SiftUp(size);
        size++;
    }

    // 堆的删除（删除根）
    void RemoveRoot()
    {
        if(size == 0)
            return;
        array[0] = array[--size];
        SiftDown(0); // 把根下沉
    }

    // 获取根
    int &GetRoot()
    {
        return array[0];
    }

    // show
    void show()
    {
        for(int i = 0; i < size; i++)
        {
            std::cout<<array[i]<< " ";
        }
        std::cout<<std::endl;
    }

private:
    int GetParent(int i) {return(i - 1) / 2;}
    int GetLeftChild(int i) {return 2 * i + 1;}
    int GetRightChild(int i) {return 2 * i + 2;}

    // 上浮操作
    void SiftUp(int i) 
    {
        while(i > 0 && array[i] < array[GetParent(i)])
        {
            std::swap(array[i], array[GetParent(i)]);
            i = GetParent(i);
        }
    }

    // 下沉操作
    void SiftDown(int i) 
    {
        int leftChild = GetLeftChild(i);
        int rightChild = GetRightChild(i);

        int Min = i;
        // 左孩子存在且值比我小
        if(leftChild < size && array[leftChild] < array[i])
        {
            Min = leftChild;
        }

        // 右孩子存在且比我和左孩子的较小值小
        if(rightChild < size && array[rightChild] < array[Min])
        {
            Min = rightChild;
        }

        if(Min != i)
        {
            std::swap(array[i], array[Min]);
            SiftDown(Min);
        }
    }
    int array[capacity];
    int size; // 当前数组元素个数
};

int main()
{
#if 0
    MinHeap h;
    for(int i = 0; i < 10; i++)
    {
        h.Insert(i + 1);
    }

    h.show();

    h.RemoveRoot();
    h.show();
#endif

#if 1
    // Top K问题
    srand(time(nullptr));
    int a[20];
    for(int i = 0; i < 20; i++)
    {
        a[i] = rand() % 100 + 1;
    }
    for(int i = 0; i < 20; i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    MinHeap h;
    // nlogn
    for(int i = 0; i < 20; i++) // n
    {
        if(i < 5)
        {
            h.Insert(a[i]);
        }
        else
        {
            if(a[i] > h.GetRoot())
            {
                h.RemoveRoot();
                h.Insert(a[i]); // 最大情况要下沉树的高度h次也就是log₂n
            }
        }
    }
    h.show();
#endif
    return 0;
}
